package demo1;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

public class Test {
    public static boolean chkPalindrome(SingleList.ListNode A) {
        //如果是空链表返回true
        if(A == null) {
            return true;
        }

        SingleList.ListNode slow = A;
        SingleList.ListNode fast = A;

        //找到中间结点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //保存fast的结点信息，避免后面反转链表丢失信息
        boolean isOdd = true;//是否是奇数个结点
        if(fast == null) {
            isOdd = false;
        }

        //反转后半部分的链表
        SingleList.ListNode prev = slow;
        SingleList.ListNode cur = slow.next;
        while(cur != null) {
            SingleList.ListNode curN = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curN;
        }

        //前后遍历链表
        SingleList.ListNode pA = A;
        SingleList.ListNode last = prev;

        //偶数个结点
        if(!isOdd) {
            while(pA.next != last) {
                if(pA.val != last.val) {
                    return false;
                }
                pA = pA.next;
                last = last.next;
            }
            if(pA.val != last.val) {
                return false;
            }
        }

        //奇数个结点
        if(isOdd) {
            while(pA != last) {
                if(pA.val != last.val) {
                    return false;
                }
                pA = pA.next;
                last = last.next;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        SingleList list = new SingleList();
        list.addLast(4);
        list.addLast(2);
        list.addLast(3);
        list.addLast(2);
        list.addLast(1);
        boolean reslut = chkPalindrome(list.head);
        System.out.println(reslut);
    }
}

class Test1 {

    public static void main5(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        System.out.println("===== ListIterator ====");
        ListIterator<Integer> lit2 =  list.listIterator(list.size());
        while (lit2.hasPrevious()) {
            System.out.print(lit2.previous()+" ");
        }
        System.out.println();
    }
    public static void main4(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        System.out.println("===== Iterator ====");
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        ListIterator<Integer> lit =  list.listIterator();
        while (lit.hasNext()) {
            System.out.print(lit.next()+" ");
        }
        System.out.println();
    }
    public static void main3(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        for(int x : list) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
    public static void main2(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        int size = list.size();
        for (int i = 0; i < size; i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
    }
    public static void main1(String[] args) {
        SingleList singleList = new SingleList();
        singleList.addFirst(1);
        singleList.addFirst(2);
        singleList.addFirst(3);
        singleList.addIndex(3,3);
        singleList.display();
        singleList.remove(2);
        singleList.display();
        singleList.clear();
        singleList.display();
    }
}
